#include "glut.h"
#include <time.h>
#include "v2d.h"
#include "templatevector.h"
#include "glutrenderingcontext.h"
#include "drawing.h"
#include <stdio.h>
#include <conio.h>

/** the screen is 600x600 pixels (a square), 50x50 standard cartesian plane */
GLUTRenderingContext g_screen(V2DF(600, 600), V2DF(-3.0,-3.0), V2DF(3.0, 3.0));

#include "solution.h"

struct BinaryTreeNode
{
	/** where to draw the node */
	V2DF pos;
	/** the value held by the node */
	int data;
	BinaryTreeNode * left;
	BinaryTreeNode * right;
	/** used for some traversal algorithms */
	int mark;
	BinaryTreeNode(int a_data, V2DF a_pos)
		:data(a_data),mark(0),left(0),right(0),pos(a_pos){}
	void add(int a_data, int depth)
	{
		if(a_data < data){
			if(left)
				left->add(a_data, depth+1);
			else		
				left = new BinaryTreeNode(a_data, 
									pos.sum(V2DF(-.5/depth, -.5)));
		}
		if(a_data > data){
			if(right)
				right->add(a_data, depth+1);
			else		
				right = new BinaryTreeNode(a_data, 
									pos.sum(V2DF(+.5/depth, -.5)));
		}
	}
	void add(int a_data)
	{
		add(a_data, 1);
	}
private:
	static const int WHITE = 0xffffff, GRAY = 0x888888;
public:
	void glDraw()
	{
		char buffer[10];
		sprintf_s(buffer, "%d", data);
		glColor3ubv((GLubyte*)&WHITE);
		pos.glDrawString(buffer);
		if(left)
		{
			left->glDraw();
			glColor3ubv((GLubyte*)&GRAY);
			pos.glDrawTo(left->pos);
		}
		if(right)
		{
			right->glDraw();
			glColor3ubv((GLubyte*)&GRAY);
			pos.glDrawTo(right->pos);
		}
	}
	static const int PRE = -1, IN = 0, POST = 1;
	void printDepthFirst(int whichFix)
	{
		if(whichFix == PRE)		printf("%d ", data);

		if(left)	left->printDepthFirst(whichFix);

		if(whichFix == IN)		printf("%d ", data);

		if(right)	right->printDepthFirst(whichFix);

		if(whichFix == POST)	printf("%d ", data);
	}

	void setAllMarks(int mark)
	{
		this->mark = mark;
		if(left)	left->setAllMarks(mark);
		if(right)	right->setAllMarks(mark);
	}
	void printBreadthFirstSearch()
	{
    //unmark all vertices
		setAllMarks(0);
    //choose some starting vertex x
		BinaryTreeNode * x = this;
    //mark x
		x->mark = 1;
    //list L = x
		TemplateVector<BinaryTreeNode*> L;
		L.add(x);
    //tree T = x
		// ??? this is just a simple collection of connected nodes
    //while L nonempty
		while(L.size() > 0)
		{
    //choose some vertex v from front of list
			BinaryTreeNode * v = L.get(0);
			L.remove(0);
    //visit v
			printf("%d ", v->data);
    //for each unmarked neighbor w
			TemplateVector<BinaryTreeNode*> neighbors;
			neighbors.clear();
			if(v->left)neighbors.add(v->left);
			if(v->right)neighbors.add(v->right);
			for(int i = 0; i < neighbors.size(); ++i)
			{
				BinaryTreeNode * w = neighbors.get(i);
				if(w->mark == 0)
				{
    //    mark w
					w->mark = 1;
    //    add it to end of list
					L.add(w);
    //    add edge vw to T
					// ??? this binary tree has no edges
				}
			}
		}
	}
};

BinaryTreeNode * head = NULL;


/**
 * @param key what keyboard key was pressed (ASCII codes)
 * @param x/y where the mouse was at the time
 * @note: the following may be helpful:<code>
int state=glutGetModifiers();
if (state & GLUT_ACTIVE_SHIFT)	// shift is pressed</code>
 */
void keyboard(unsigned char key, int x, int y)
{
	switch(key)
	{
	case ' ':
		break;
	}
	glutPostRedisplay();
}

/** @param a_width/a_height new dimensions of the resized window */
void reshape(int a_width, int a_height)
{
	// have the graphics context calculate the changes...
	g_screen.reshape(a_width, a_height);
	glutPostRedisplay();
}

/** @param x/y the coordinate of where the mouse is */
void passiveMotion(int x, int y)
{
}

/** @param x/y the coordinate of where the mouse is being dragged */
void draggedMotion(int x, int y)
{
	if(g_selected)
	{
		V2DF click = g_screen.convertPixelsToCartesian(V2DF(x,y));
		g_selected->set(click);
	}
}

/** 
 * @param button (GLUT_LEFT_BUTTON || GLUT_MIDDLE_BUTTON || GLUT_RIGHT_BUTTON)
 * @param state (GLUT_DOWN || GLUT_UP)
 * @param x/y the coordinate of where the mouse is being dragged
 */
void mouse(int button, int state, int x, int y)
{
	switch(button)
	{
	case GLUT_LEFT_BUTTON:
		switch(state)
		{
		case GLUT_DOWN:
			{
				V2DF click = g_screen.convertPixelsToCartesian(V2DF(x,y));
				V2DF * closest = &g_points[0];
				float dist = closest->distance(click);
				float minDist = dist;
				for(int i = 0; i < g_pointsSize; ++i)
				{
					dist = g_points[i].distance(click);
					if(dist < minDist)
					{
						minDist = dist;
						closest = &g_points[i];
					}
				}
				if(minDist < RANGE)
				{
					g_selected = closest;
				}
				else
				{
					g_selected = 0;
				}
			}
			break;
		case GLUT_UP:
			g_selected = 0;
			break;
		}
		break;
	}
	glutPostRedisplay();
}

/** @return true if the game changed state and should redraw */
bool update(int a_ms)
{
	g_body.update();
	return true;
}

/** call this function every value seconds*/
void updateTimerFunction(int value)
{
	/** keeps track of when the update method was called last */
	static clock_t g_lastTime = 0;
	// what time is it now?
	clock_t now = clock();
	// how much time has passed since update was called?
	clock_t passed = now-g_lastTime;
	// if update based on time
	if(update(passed))
	{
		// ask to refresh the display
		glutPostRedisplay();
	}
	// remember this last time that update started.
	g_lastTime = now;
	now = clock();
	// calc how long it took update to process, and factor that into the next wait
	passed = now - g_lastTime;
	int waitToCall = value-passed;
	if(waitToCall < 0)waitToCall = 0;
	// queue update again, factoring in the time update just took
	glutTimerFunc(waitToCall, updateTimerFunction, value);
}

void display()
{
	glClear(GL_COLOR_BUFFER_BIT);	//Clear the screen
	int red = 0x0000ff, gray = 0x888888, white = 0xffffff;
	V2DF a(0,0), b(1,1);
	glColor3ubv((GLubyte*)&gray);
	g_screen.glDraw(0.5);			// draw the cartisian plane in white
	glColor3ubv((GLubyte*)&red);
	g_body.draw();
	if(g_selected)
	{
		glDrawCircle(*g_selected, .1);
	}
	glColor3ubv((GLubyte*)&white);
	head->glDraw();
	glFlush();						// print everything to the (off?) screen buffer
	glutSwapBuffers();				// swap the draw buffers
}

void init()
{
	// setup the screen using the graphics context
	g_screen.glSetupScreen();
	// define the drawing mode
	glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);
	//Create our window
	glutCreateWindow("data structures");
	// setup the call-back functions
    glutDisplayFunc(display);
	glutKeyboardFunc(keyboard);
	glutReshapeFunc(reshape);
	glutPassiveMotionFunc(passiveMotion);
	glutMotionFunc(draggedMotion);
	glutMouseFunc(mouse);

	g_body.init();

	// give the binary tree some data
	head = new BinaryTreeNode(12, V2DF(0,0));
	int numbers[] = {2,1,5,15,18,16,20,13};
	int countNumbers = sizeof(numbers)/sizeof(numbers[0]);
	for(int i = 0; i < countNumbers; ++i)
	{
		head->add(numbers[i]);
	}

	head->printDepthFirst(BinaryTreeNode::PRE);
	printf("\n");
	head->printDepthFirst(BinaryTreeNode::IN);
	printf("\n");
	head->printDepthFirst(BinaryTreeNode::POST);
	printf("\n\n");
	head->printBreadthFirstSearch();
	printf("\n");
}

int main(int argc, char ** argv)
{
	// initialize GLUT
	glutInit(&argc, argv);
	// initialize the application
	init();
	// start the update timer-thread game-loop
	glutTimerFunc(0, updateTimerFunction, 50);

	// abstracted game loop that we don't get to see!!!
    glutMainLoop();
	return 0;
}